《离散数学》第一学期期末试卷C (精选07)

一、选择题(每题2分，共20分)

下列语句是命题的有 [ ]。
- A. 明天下午开会吗？
- B. 2014 年元旦是星期六;
- C. $$5x + 1 > 11$$
- D. 请保持安静!

查看答案与解析

答案：B

解析：
本题考查命题的定义。

第一步：分析命题的基本特征
命题是一个陈述句，并且能够判断其真假（具有确定唯一的真值）。
第二步：逐一审查各选项
- A 是疑问句，不能判断真假，不是命题。
- B 是陈述句，具有确定的真假（无论 2014 年元旦实际上是星期几，它都有明确的真值），属于命题。
- C 是开语句，其真假取决于自变量 $$x$$ 的取值，当前无法判断真假，不是命题。
- D 是祈使句，不是命题。

故选 B。

方法总结：判断命题的两个关键点：

是否为陈述句。
真值是否唯一确定（不论真假均可）。

难度: ⭐
考点: #命题的定义 #命题真值

💡 学习锦囊

📖 相关公式与知识点:

命题定义：陈述客观事实且具有唯一真值的陈述句。
疑问句、感叹句、祈使句以及开语句均不是命题。

思路分析

解题关键在于判断句子是否为“陈述句”以及“是否有唯一确定的真值”。

易错点

误认为“错误的陈述”不是命题。注意：假命题也是命题，只要它真值确定即可。

🔄 举一反三

下列哪个是命题？
- A. $\pi$ 是无理数。
- B. 请把门关上。
查看练习答案与解析
答案：A
解析：A 是陈述句且真值为真。

下列命题公式中，哪个是永真式 [ ]。
- A. $p \wedge \neg q$
- B. $p \to q$
- C. $(\neg p \lor q) \lor p$
- D. $(\neg p \wedge q) \wedge p$

查看答案与解析

答案：C

解析：
本题考查永真式（重言式）的判定。

方法一：等值演算
利用析取的结合律和交换律对 C 选项进行化简：
$(\neg p \lor q) \lor p \equiv (\neg p \lor p) \lor q$
根据排中律， $\neg p \lor p \equiv T$ （真）：
$T \lor q \equiv T$
公式恒为真，因此是永真式。
方法二：分析其余选项
- A、B 在某些赋值下为假（例如 $$p=F$$ 时 A 为假， $$p=T, q=F$$ 时 B 为假）。
- D 化简得 $\neg p \wedge p \wedge q \equiv F \wedge q \equiv F$ （永假式）。

故选 C。

难度: ⭐
考点: #永真式 #等值演算 #排中律

💡 学习锦囊

📖 相关公式与知识点:

排中律： $p \lor \neg p \equiv T$
矛盾律： $p \land \neg p \equiv F$

思路分析

观察公式中是否有能应用排中律化简的部分，若能最终化简为 $$T$$ ，则为永真式。

易错点

公式符号极易看混，请严格区分合取 $\land$ 与析取 $\lor$ 的优先级和规律。

🔄 举一反三

判断公式 $\neg (p \land \neg p)$ 是否为永真式。
查看练习答案与解析
答案：是
解析：根据矛盾律， $p \land \neg p \equiv F$ ，故否定后 $\neg F \equiv T$ 为永真式。

$A = \{a, b, c\}$ ，在下列 $A$ 上的二元关系中，不具有反对称性的是 [ ]。
- A. $\{\langle a, a \rangle, \langle b, b \rangle\}$
- B. $\{\langle a, b \rangle, \langle b, a \rangle\}$
- C. $\{\langle a, a \rangle, \langle a, b \rangle\}$
- D. $\{\langle a, b \rangle, \langle b, c \rangle\}$

查看答案与解析

答案：B

解析：
本题考查二元关系的反对称性。

第一步：理解反对称性定义
对于集合 $$A$$ 上的关系 $$R$$ ，如果 $\langle x, y \rangle \in R$ 且 $\langle y, x \rangle \in R$ ，则必有 $$x = y$$ 。换言之，若 $x \neq y$ ，则 $\langle x, y \rangle$ 与 $\langle y, x \rangle$ 不能同时存在于 $$R$$ 中。
第二步：审查选项
- B 选项中包含 $\langle a, b \rangle$ 和 $\langle b, a \rangle$ ，且 $a \neq b$ ，这直接违背了反对称性的要求。

故选 B。

难度: ⭐⭐
考点: #二元关系性质 #反对称性

💡 学习锦囊

📖 相关公式与知识点:

反对称性定义： $\forall x, y \in A, (\langle x, y \rangle \in R \land \langle y, x \rangle \in R \to x = y)$ 。

思路分析

寻找关系中是否存在元素相异的 $\langle x, y \rangle$ 和 $\langle y, x \rangle$ 。只要有一对，就不具反对称性。

易错点

不要将“反对称性”与“不对称性”混淆，反对称性允许 $\langle a, a \rangle$ 这种自环式元组存在。

🔄 举一反三

关系 $R = \emptyset$ 是否在非空集合 $$A$$ 上具有反对称性？
查看练习答案与解析
答案：是
解析：条件“ $\langle x, y \rangle \in R \land \langle y, x \rangle \in R$ ”无法满足，属于真空成立。

若 $M = \{1, 2, 3, 4\}$ ，则下列集合中，哪个是 $M$ 的划分 [ ]。
- A. $\{\{1, 2, 3\}, \{2, 3, 4\}\}$
- B. $\{\{1\}, \{2, 3\}\}$
- C. $\{\emptyset ,\{1\} ,\{2,3\} ,\{4\} \}$
- D. $\{\{1, 3\}, \{2, 4\}\}$

查看答案与解析

答案：D

解析：
本题考查集合划分的概念。

第一步：掌握划分的充要条件
集合 $M$ 的划分是子集构成的集合，必须满足：
1. 每个子集均非空。
2. 所有子集的并集等于原集合 $$M$$ 。
3. 任意两个不同的子集不相交（交集为空）。
第二步：评估各选项
- A 中两个子集交集为 $\{2, 3\} \neq \emptyset$ ，不合题意。
- B 中元素少于原集（漏了元素 4），不合题意。
- C 中包含空集 $\emptyset$ ，不合题意。
- D 中， $\{1, 3\} \cup \{2, 4\} = M$ 且 $\{1, 3\} \cap \{2, 4\} = \emptyset$ ，完全满足划分定义。

故选 D。

难度: ⭐⭐
考点: #集合的划分 #集合论

💡 学习锦囊

📖 相关公式与知识点:

划分条件： $\bigcup A_i = M$ ， $A_i \cap A_j = \emptyset (i \neq j)$ ，且 $A_i \neq \emptyset$ 。

易错点

易遗漏子集必须非空的条件（排除空集）。
务必检查并集是否完整覆盖原集。

🔄 举一反三

集合 $S = \{a, b\}$ 的所有可能划分有几个？
查看练习答案与解析
答案：2个
解析：划分 1 为 $\{\{a, b\}\}$ ，划分 2 为 $\{\{a\}, \{b\}\}$ 。

设 $A = \{a, b\}$ 、 $B = \{1, 2\}$ ，$R_1$ 、 $R_2$ 、 $R_3$ 、 $R_4$ 都是 $A$ 到 $B$ 的二元关系，
- A. $R_{1} = \{\langle a, 1 \rangle, \langle b, 2 \rangle\}$
- B. $R_2 = \{\langle a, 1 \rangle, \langle b, 1 \rangle, \langle b, 2 \rangle\}$
- C. $R_3 = \{\langle a, 1 \rangle, \langle a, 2 \rangle\}$
- D. $R_4 = \{\langle a, 1 \rangle, \langle b, 1 \rangle\}$ 则 $$A$$ 到 $$B$$ 的函数是 [ ]

查看答案与解析

答案：A（或 D）

解析：
本题考查函数的定义。

第一步：明确 $$A$$ 到 $$B$$ 的函数的条件
对于关系 $R \subseteq A \times B$ ，若 $\forall x \in A$ ，在 $$B$$ 中都有唯一确定的 $$y$$ 使得 $\langle x, y \rangle \in R$ ，则 $$R$$ 是从 $$A$$ 到 $$B$$ 的函数。
第二步：检验各个选项
- A： $$R_1$$ 中 $a \to 1, b \to 2$ ，所有 $$A$$ 中的元素都有唯一对应象，是函数。
- B：元素 $$b$$ 映射到 1 和 2，不是函数。
- C：元素 $$a$$ 映射到两个值，且没有给 $$b$$ 分配映射，不是函数。
- D： $$R_4$$ 中 $a \to 1, b \to 1$ ，也是合法的函数（常数映射）。

注：题目设计存在多选性质，A 和 D 均符合函数定义，本题以 A 为代表答案。

难度: ⭐⭐
考点: #函数定义 #映射

💡 学习锦囊

📖 相关公式与知识点:

函数的单值性： $\forall x \in A, \forall y_1, y_2 \in B, (\langle x, y_1 \rangle \in R \land \langle x, y_2 \rangle \in R \to y_1 = y_2)$ 。

思路分析

检查 $$A$$ 中的每一个元素是否在关系中有且仅出现了一次作为第一坐标。

易错点

函数定义要求定义域中的所有元素都必须有对应的象，不能漏掉元素。

🔄 举一反三

$R = \{\langle a, 1 \rangle\}$ 是否是从 $\{a, b\}$ 到 $\{1\}$ 的函数？
查看练习答案与解析
答案：否
解析：因为定义域中的元素 $$b$$ 在 $$R$$ 中没有对应的象。

有向图的关联矩阵中, 每列的元素之和为 [ ]。
- A. 0
- B. 2
- C. 边数
- D. 不确定

查看答案与解析

答案：A

解析：
本题考查有向图关联矩阵的定义与性质。

第一步：理解关联矩阵的构成
有向图的关联矩阵 $$M$$ 中，行对应顶点，列对应有向边。
第二步：分析各列元素的和
对于任意不带自环的有向边 $e_k = \langle v_i, v_j \rangle$：
- 起点 $$v_i$$ 对应的矩阵元素为 1（或 -1）。
- 终点 $$v_j$$ 对应的矩阵元素为 -1（或 1）。
- 该列其余所有元素均为 0。因此，对每列元素求和，结果总是 $$(1) + (-1) = 0$$ 。

故选 A。

难度: ⭐⭐
考点: #有向图 #关联矩阵

💡 学习锦囊

📖 相关公式与知识点:

关联矩阵性质：每列对应一条边，仅在起、终点处非零。

思路分析

关注关联矩阵中“每列”和“每行”的含义差异（每列是边，每行是点）。

🔄 举一反三

无向图的关联矩阵中，每列元素的和为？
查看练习答案与解析
答案：2
解析：每条边关联两个顶点，无向边在关联顶点行均为 1。

下图中，是哈密尔顿图的为 [ ]。

查看答案与解析

答案：B

解析：
本题考查哈密尔顿图的识别。

第一步：掌握哈密尔顿图的充要特征
哈密尔顿图是包含哈密尔顿圈的图。哈密尔顿圈需要恰好经过图中的每一个顶点一次。
第二步：排除带有割顶的图
- 图 A 和图 C 中，均存在割顶（去除该顶点后图会变得不连通），具有割顶的图不可能包含哈密尔顿圈，排除 A、C。
第三步：排除含有度数为 1 顶点的图
- 图 D 中存在度数为 1 的悬挂顶点，哈密尔顿圈必须经过所有顶点且每个顶点度数至少为 2。
第四步：检验 B 选项
- 图 B 是一典型的四阶完全图（正方形加对角线），我们可以很容易地沿着其外围构成一个圈：例如左上 $\to$ 右上 $\to$ 右下 $\to$ 左下 $\to$ 左上。

故选 B。

难度: ⭐⭐
考点: #图论 #哈密尔顿图 #割顶

💡 学习锦囊

📖 相关公式与知识点:

哈密尔顿图必要条件：无割顶、无悬挂点。

易错点

哈密尔顿图强调的是“经过所有顶点”的圈，而欧拉图强调的是“经过所有边”的圈。

🔄 举一反三

五阶轮图 $$W_5$$ 是否是哈密尔顿图？
查看练习答案与解析
答案：是
解析：轮图的边缘节点首尾相连构成一个圈，只需包含中心即可扩展。

下列四组数据中，不能成为任何图的度数序列的为 [ ]。
- A. 1, 2, 3, 4
- B. 3, 2, 2, 3
- C. 4, 2, 2, 3
- D. 2, 2, 4, 4

查看答案与解析

答案：C

解析：
本题考查握手定理与图的度数序列判定。

握手定理：任何图中，所有顶点的度数之和等于边数的两倍（ $\sum d(v_i) = 2m$ ）。
核心结论：度数和必须是偶数，奇数度的顶点个数必须为偶数。
逐项相加各组度数：
- A： $$1+2+3+4 = 10$$ （偶数，合法）
- B： $$3+2+2+3 = 10$$ （偶数，合法）
- C： $$4+2+2+3 = 11$$ （奇数，完全无法构成任何图）
- D： $$2+2+4+4 = 12$$ （偶数，合法）

故选 C。

难度: ⭐
考点: #握手定理 #图的度数序列

💡 学习锦囊

📖 相关公式与知识点:

$\sum_{v \in V} d(v) = 2|E|$ 。

易错点

牢记握手定理对任何图（含重边、自环）都成立，首要任务是判断奇偶性。

🔄 举一反三

度数序列 $\{1, 1, 3\}$ 是否能构成图？
查看练习答案与解析
答案：不能
解析：度数和为 5，不满足握手定理。

设 $D$ 为具有 5 个顶点 5 条边的有向简单图，则其补图的边数为 [ ]。
- A. 20
- B. 15
- C. 10
- D. 5

查看答案与解析

答案：B

解析：
本题考查有向简单图的补图概念。

第一步：计算完全有向图的边数
在有向简单图中，顶点数 $$n=5$$ ，任意两个顶点之间允许双向存在有向边。总共允许的最大边数为： $n(n-1) = 5 \times 4 = 20$ 条。
第二步：计算补图边数
补图定义下，补图边数 = 最大边数 - 原图边数 = $$20 - 5 = 15$$ 条。

故选 B。

难度: ⭐⭐
考点: #有向图 #补图

💡 学习锦囊

📖 相关公式与知识点:

$$n$$ 阶无向完全图边数： $$n(n-1)/2$$ 。
$$n$$ 阶有向完全图边数： $$n(n-1)$$ 。

易错点

注意区分“无向图”与“有向图”，最大边数不同。

🔄 举一反三

无向图有 5 个顶点 3 条边，补图的边数是多少？
查看练习答案与解析
答案：7
解析：最大边数 $5 \times 4 / 2 = 10$ ，补图边数为 $$10 - 3 = 7$$ 。

设 $R$ 是集合 $A$ 上的二元关系，那么 $R$ 的对称闭包 $s(R) = [\quad]$
- A. $R \cap I_A$
- B. $R \cup I_A$
- C. $R \cup R^{-1}$
- D. $R \cap R^{-1}$

查看答案与解析

答案：C

解析：
本题考查对称闭包的代数定义。

对称闭包 $$s(R)$$ 指包含关系 $$R$$ 且具备对称性的最小二元关系。
构造对称关系的核心就是把关系 $$R$$ 中的所有有序对的逆元也包含进来，公式为 $s(R) = R \cup R^{-1}$ 。

故选 C。

难度: ⭐
考点: #关系的闭包 #对称闭包

💡 学习锦囊

📖 相关公式与知识点:

自反闭包： $r(R) = R \cup I_A$ 。
传递闭包： $t(R) = R \cup R^2 \cup R^3 \dots$

思路分析

对称即是有 $\langle x,y \rangle$ 必有 $\langle y,x \rangle$ ，利用逆关系 $R^{-1}$ 补齐。

🔄 举一反三

求 $R = \{\langle 1, 2 \rangle\}$ 的对称闭包。
查看练习答案与解析
答案： $\{\langle 1, 2 \rangle, \langle 2, 1 \rangle\}$
解析：直接应用公式 $R \cup R^{-1}$ 。

二、填空题(每题2分，共20分)

设 $$F(x)$$ ： $$x$$ 是运动员， $$G(x)$$ ： $$x$$ 是大学生，命题“不是所有的运动员都是大学生。”谓词符号化为 ______________。

查看答案与解析

答案： $\neg \forall x(F(x) \to G(x))$ 或 $\exists x(F(x) \land \neg G(x))$

解析：

直译法：“所有的运动员都是大学生”译为 $\forall x (F(x) \to G(x))$ ，“不是所有”加否定词 $\neg$ 即可。
等值转换： $\neg \forall x(F(x) \to G(x)) \equiv \exists x \neg (\neg F(x) \lor G(x)) \equiv \exists x (F(x) \land \neg G(x))$ （存在一些运动员不是大学生）。

难度: ⭐⭐
考点: #谓词符号化

💡 学习锦囊

📖 相关公式与知识点:

$\forall$ 通常与蕴含 $\to$ 配合。
$\exists$ 通常与合取 $\land$ 配合。

思路分析

理清“否定所有的”相当于“存在一个不满足”。

易错点

量词外提时，条件前件的否定会导致逻辑符号的变化，请留意。

🔄 举一反三

将“所有的人都是要死的”符号化。
查看练习答案与解析
答案： $\forall x(H(x) \to M(x))$

谓词公式 $\forall x\exists y P(x,y)$ 的真值为 ________，其中， $$P(x,y)$$ ： $$x = y$$ ，定义域： $D = \{1, 2\}$ 。

查看答案与解析

答案：真

解析：
公式含义为：对于定义域 $$D$$ 中的每一个元素 $$x$$ ，都存在 $$D$$ 中的一个元素 $$y$$ ，使得 $$x = y$$ 。

当 $$x=1$$ 时，可令 $$y=1$$ ，满足 $$1=1$$ ；
当 $$x=2$$ 时，可令 $$y=2$$ ，满足 $$2=2$$ 。条件均满足，因此公式为真。

难度: ⭐
考点: #谓词公式的真值

💡 学习锦囊

📖 相关公式与知识点:

注意量词顺序， $\forall x \exists y$ 与 $\exists y \forall x$ 并不等价。

🔄 举一反三

谓词公式 $\exists x \forall y P(x,y)$ 的真值为？
查看练习答案与解析
答案：假
解析：不存在一个元素使得它和定义域中所有元素都相等。

公式 $\forall xF(x,z) \to \exists yG(x,y)$ 的前束范式是 ______________。

查看答案与解析

答案： $\exists u \exists y (F(u,z) \to G(x,y))$

解析：

第一步：重命名约束变量
原公式中 $\exists y G(x,y)$ 里的 $$x$$ 是自由变量，应将前驱 $\forall x F(x,z)$ 的 $$x$$ 改名，化为 $\forall u F(u,z) \to \exists y G(x,y)$ 。
第二步：量词外提规则
前件的 $\forall u$ 在条件前被提取出来变为 $\exists u$ ： $\exists u [F(u,z) \to \exists y G(x,y)]$ 。再将 $\exists y$ 顺理外提： $\exists u \exists y (F(u,z) \to G(x,y))$ 。

难度: ⭐⭐⭐
考点: #前束范式 #量词提取

💡 学习锦囊

📖 相关公式与知识点:

$(\forall x A) \to B \equiv \exists x (A \to B)$ 。
$A \to (\exists y B) \equiv \exists y (A \to B)$ 。

思路分析

切记不要改动公式中的自由变量。

🔄 举一反三

求 $\exists x F(x) \lor \forall y G(y)$ 的前束范式。
查看练习答案与解析
答案： $\exists x \forall y (F(x) \lor G(y))$

$A = \{a, b, c\}$ ，则 $$A$$ 上定义的所有二元关系中，具有自反性的有 ______ 个。

查看答案与解析

答案：64

解析：

$A \times A$ 中共有 $3 \times 3 = 9$ 个有序对。
自反关系必须无条件包含自反轴元素 $\langle a,a \rangle, \langle b,b \rangle, \langle c,c \rangle$ （3个）。
剩下的 $$9 - 3 = 6$$ 个有序对，均有“包含/不包含”2 种选项，所以总计 $$2^6 = 64$$ 个。

难度: ⭐⭐
考点: #自反关系 #排列组合

💡 学习锦囊

📖 相关公式与知识点:

自反的充要条件是 $I_A \subseteq R$ 。

🔄 举一反三

集合 $A=\{a, b, c\}$ 上对称关系的数量为？
查看练习答案与解析
答案：64
解析：主对角线 3 个位置加上上三角 3 个独立位置，共有 6 处自主选择， $$2^6 = 64$$ 。

设 $A = \{a, b, c, d\}$ ， $$A$$ 上的等价关系 $R = \{\langle a, c \rangle, \langle c, a \rangle, \langle d, b \rangle, \langle b, d \rangle\} \cup I_{\mathrm{A}}$ ，则商集 $$A / R = $$ ______________。

查看答案与解析

答案： $\{\{a, c\}, \{b, d\}\}$

解析：

根据 $$I_A$$ 及题目数据，元素 $$a$$ 与 $$c$$ 互相等价，形成等价类 $\{a, c\}$ 。
元素 $$b$$ 与 $$d$$ 互相等价，形成等价类 $\{b, d\}$ 。
商集由这些等价类构成，即 $\{\{a, c\}, \{b, d\}\}$ 。

难度: ⭐⭐
考点: #等价类 #商集

💡 学习锦囊

📖 相关公式与知识点:

等价关系必定能诱导出商集划分。

🔄 举一反三

给出划分 $\{\{1\}, \{2, 3\}\}$ ，求其对应的等价关系。
查看练习答案与解析
答案： $\{\langle 1,1 \rangle, \langle 2,2 \rangle, \langle 3,3 \rangle, \langle 2,3 \rangle, \langle 3,2 \rangle\}$

若无向树 $$T$$ 有 4 个 3 度结点, 3 个 2 度结点, 其余均为 1 度结点, 则该树共有 ______ 个结点。

查看答案与解析

答案：13

解析：
设 1 度结点有 $$x$$ 个，总结点 $$n = 4 + 3 + x = 7 + x$$ 。树的边数 $$m = n - 1 = 6 + x$$ 。依据握手定理 $\sum d(v_i) = 2m$ ：

4 \times 3 + 3 \times 2 + x \times 1 = 2(6+x)

18 + x = 12 + 2x \implies x = 6

总节点数为 $$7 + 6 = 13$$ 。

难度: ⭐⭐
考点: #无向树 #握手定理

💡 学习锦囊

📖 相关公式与知识点:

树边数定理： $$m = n - 1$$ 。

🔄 举一反三

假设一个无向树有 2 个 2 度顶点，3 个 3 度顶点，其余为 1 度，求 1 度顶点个数。
查看练习答案与解析
答案：5
解析：列方程求解得。

$$n$$ 阶无向完全图 $K_n (n \ge 3)$ 为欧拉图的条件为 ______________。

查看答案与解析

答案：n 为奇数

解析：
完全图中每个节点的度数都是 $$n-1$$ 。欧拉图要求节点的度数为偶数 $\implies n-1$ 是偶数 $\implies n$ 为奇数。

难度: ⭐
考点: #欧拉图 #完全图

💡 学习锦囊

📖 相关公式与知识点:

欧拉图条件：全图连通且顶点均为偶数度。

🔄 举一反三

轮图 $$W_n$$ 何时是欧拉图？
查看练习答案与解析
答案： $$n$$ 为奇数

4 阶无向完全图是平面图，则该图的面数为 ______。

查看答案与解析

答案：4

解析：
$$K_4$$ 顶点 $$n=4$$ ，边数 $m = 4 \times 3 / 2 = 6$ 。欧拉公式： $n - m + r = 2 \implies 4 - 6 + r = 2 \implies r = 4$ 。

难度: ⭐⭐
考点: #平面图 #欧拉公式

💡 学习锦囊

📖 相关公式与知识点:

欧拉公式： $$V - E + F = 2$$ 。

🔄 举一反三

$$K_3$$ 的面数是？
查看练习答案与解析
答案：2
解析：一个内部面，一个外部无限面。

若集合 $A = \{a, b\}$ 。则其幂集 $$P(A) = $$ ______________。

查看答案与解析

答案： $\{\emptyset, \{a\}, \{b\}, \{a, b\}\}$

难度: ⭐
考点: #幂集

💡 学习锦囊

📖 相关公式与知识点:

幂集大小为 $$2^n$$ 。

🔄 举一反三

$P(\emptyset)$ 是多少？
查看练习答案与解析
答案： $\{\emptyset\}$

设 $$G$$ 是任意的连通平面图，顶点数为 $$n$$ ，边数为 $$m$$ ，面数为 $$r$$ ，则三者具有的关系为（欧拉公式）；对于任意的 $$p$$ （ $$p>1$$ ）个的连通分支的平面图，则它们的关系为（欧拉公式的推广）。

查看答案与解析

答案： $$n - m + r = 2$$ ； $$n - m + r = p + 1$$

解析：

连通平面图的欧拉公式即为经典的 $$V - E + F = 2$$ 。
对于非连通图，若有 $$p$$ 个连通分量，则公式推广为 $$n - m + r = p + 1$$ 。

难度: ⭐
考点: #欧拉公式

💡 学习锦囊

📖 相关公式与知识点:

连通分支推广式。

🔄 举一反三

有 2 个分支时公式表现如何？
查看练习答案与解析
答案： $$n - m + r = 3$$

三、综合题(第1~6题每题8分，第7题12分，共60分)

求命题公式 $((p \to q) \lor r) \land (\neg p \to r)$ 的主析取范式、主合取范式以及成真赋值、成假赋值。

查看答案与解析

答案：
主析取范式为： $m_1 \lor m_3 \lor m_5 \lor m_6 \lor m_7$ ；
主合取范式为： $M_0 \land M_2 \land M_4$ ；
成真赋值：001, 011, 101, 110, 111；
成假赋值：000, 010, 100。

解析：
进行命题等值演算：

A \equiv (\neg p \lor q \lor r) \land (p \lor r)

当赋值为 $$p=0, q=0, r=0$$ 时， $A \equiv F$ (成假) $\implies M_0$
当赋值为 $$p=0, q=1, r=0$$ 时， $A \equiv F$ (成假) $\implies M_2$
当赋值为 $$p=1, q=0, r=0$$ 时， $A \equiv F$ (成假) $\implies M_4$
所有的极小项总和排除这三项，主析取范式为： $\sum(1, 3, 5, 6, 7)$ 。

难度: ⭐⭐
考点: #主范式

💡 学习锦囊

📖 相关公式与知识点:

极小项与极大项的转换。

🔄 举一反三

求 $p \lor q$ 的主析取范式。
查看练习答案与解析
答案： $m_1 \lor m_2 \lor m_3$

在自然推理系统中，构造下面推理证明：（1）如果他是理科学生，他一定要学数学；如果他不是文科学生，他一定是理科学生。他没有学数学。所以他是文科学生。
（2）在命题逻辑中构造下面推理的证明：前提： $p \to q$ ， $(\neg q \lor r) \land \neg r$ ， $p \lor \neg s$ ；结论： $\neg s$ 。

查看答案与解析

答案：
（1）证明：设 $$P$$ ：他是理科生； $$Q$$ ：他要学数学； $$R$$ ：他是文科生。已知： $P \to Q, \neg R \to P, \neg Q$

$P \to Q$ (Premise)
$\neg Q$ (Premise)
$\neg P$ (MT 拒取式)
$\neg R \to P$ (Premise)
$\neg\neg R \equiv R$ (MT 拒取式) 结论成立。

（2）证明：

$(\neg q \lor r) \land \neg r$ (Premise)
$\neg r$ (Simp 化简)
$\neg q \lor r$ (Simp 化简)
$\neg q$ (析取三段论)
$p \to q$ (Premise)
$\neg p$ (MT 拒取式)
$p \lor \neg s$ (Premise)
$\neg s$ (析取三段论) 证毕。

难度: ⭐⭐
考点: #自然推理证明

💡 学习锦囊

📖 相关公式与知识点:

拒取式： $A \to B, \neg B \implies \neg A$ 。

🔄 举一反三

试证明公式 $p \to (p \lor q)$ 是永真的。
查看练习答案与解析
答案：证明：1. $$p$$ (附加前提) 2. $p \lor q$ (附加律) 3. $p \to (p \lor q)$ (CP规则)。

若 $A = \{1, 2, 3, 4\}$ ，找出 $$A$$ 上的等价关系 $$R$$ ，该等价关系 $$R$$ 能诱导出 $$A$$ 的划分 $\{\{1, 2\}, \{3\}, \{4\}\}$ 。（1）写出等价关系 $$R$$ 的集合式；
（2）画出等价关系 $$R$$ 的关系图；
（3）写出 $$R^2$$ 的集合式。

查看答案与解析

答案：
（1） $R = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle\}$
（2）顶点 $\{1, 2, 3, 4\}$ ，1与2之间存在双向箭头，且每个节点均带有指向自己的自环。
（3）由于等价关系具传递性，故 $R^2 = R = \{\langle 1, 1 \rangle, \langle 2, 2 \rangle, \langle 1, 2 \rangle, \langle 2, 1 \rangle, \langle 3, 3 \rangle, \langle 4, 4 \rangle\}$ 。

难度: ⭐⭐
考点: #等价关系 #关系矩阵

💡 学习锦囊

📖 相关公式与知识点:

关系的乘法定义。

🔄 举一反三

已知 $R = \{\langle 1,2 \rangle\}$ ，求 $$t(R)$$ 。
查看练习答案与解析
答案： $\{\langle 1,2 \rangle\}$

设集合 $A = \{ 2, 3, 6, 8, 9, 12, 18, 24\}$ ， $$R$$ 为整除关系。（1）画出偏序集 $\langle A, R \rangle$ 的哈斯图；
（2）写出 $B = \{2, 3, 6\}$ 的极大元、极小元；
（3）写出 $C = \{6, 12, 18\}$ 的上界、下界。

查看答案与解析

答案：
（1）哈斯图分层从下到上依次为：

底层（极小元）：2, 3
2楼：6（接自2, 3），8（接自2），9（接自3）
3楼：12（接自6, 8），18（接自6, 9）
顶层：24（接自12）（2）极大元：6；极小元：2, 3。
（3）上界：无；下界：2, 3, 6。

难度: ⭐⭐
考点: #整除关系 #哈斯图 #界与极值

💡 学习锦囊

📖 相关公式与知识点:

哈斯图绘制规律。

🔄 举一反三

画出 $A=\{1,2,3,6\}$ 的整除哈斯图。
查看练习答案与解析
答案：底层为 1，中间为 2 和 3（均与 1 相连），顶层为 6（与 2, 3 相连）。

图 $$G$$ 是一个简单且连通的平面图，顶点数为 11，其无限面的次数为 8，其余有限面的次数都为 6，计算平面图 $$G$$ 的边数 $$m$$ 和面数 $$r$$ 。

查看答案与解析

答案：边数 13，面数 4。

解析：
根据平面图的面次数定理：所有面的次数之和等于 $$2m$$ 。设面数为 $$r$$ ：

8 + 6(r-1) = 2m \implies 2m - 6r = 2 \implies m - 3r = 1 \quad \dots(1)

依据连通图欧拉公式：

11 - m + r = 2 \implies m - r = 9 \quad \dots(2)

由 (2) 得 $$m = r + 9$$ ，代入 (1)：

(r+9) - 3r = 1 \implies -2r = -8 \implies r = 4

则 $$m = 4 + 9 = 13$$ 。

难度: ⭐⭐
考点: #平面图公式

💡 学习锦囊

📖 相关公式与知识点:

$2E = \sum \text{deg}(F)$ 。

🔄 举一反三

变式题：若所有面度数均为 3，且有 6 个点，求面数。
查看练习答案与解析
答案：8

有向图 $$G$$ 如右图所示：（1）写出图 $$G$$ 的邻接矩阵、可达矩阵；
（2）求该图中长度为 2 的通路总数、回路总数；
（3）判断该图是否为强连通图？
（4）判断该图是否为欧拉图？

查看答案与解析

答案：
（1） $ $A = \begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}, \quad P = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$ $$ （2）长度为 2 的通路总数为 10；回路总数为 3。（3）是强连通图（每对顶点互相可达）。（4）不是欧拉图（存在顶点入度不等于出度，如 $$ d_{in}(v_2)=2 \neq d_{out}(v_2)=3$）。

难度: ⭐⭐⭐
考点: #有向图矩阵 #通路与回路

💡 学习锦囊

📖 相关公式与知识点:

矩阵乘法在图论中的应用。

🔄 举一反三

变式题：若要求长度为 3 的通路总数，应如何计算？
查看练习答案与解析
答案：计算 $$A^3$$ ，矩阵中所有元素之和即为长度为 3 的通路总数。

某中学有 3 个课外小组：物理组、化学组、生物组。今有张、王、李、赵、陈 5 名同学, 若已知: （1）张、王为物理组成员，张、李、赵为化学组成员，李、赵、陈为生物组成员；
（2）张为物理组成员, 王、李、赵为化学组成员, 王、李、赵、陈为生物组成员;
（3）张为物理组和化学组成员，王、李、赵、陈为生物组成员。问在以上 3 种情况下能否各选出 3 名不兼任的组长？

查看答案与解析

答案：
（1）能。
（2）能。
（3）不能。

解析：
运用 Hall 结婚定理（相异代表系）。

情况（1）：并集检验 $|S_1 \cup S_2| = 4 \ge 2, \dots$ ，均满足并集元素个数大于等于子集数，故可行。
情况（3）： $S_1 = \{\text{张}\}, S_2 = \{\text{张}\}$ ，其并集 $|S_1 \cup S_2| = |\{\text{张}\}| = 1 < 2$ ，违背 Hall 条件，故无法实现。

难度: ⭐⭐⭐
考点: #Hall定理 #相异代表系

💡 学习锦囊

📖 相关公式与知识点:

Hall 定理充分必要条件。

🔄 举一反三

变式题：如果有 3 个集合，且任意 2 个集合的并集大小至少为 2，任意 3 个集合的并集大小至少为 3，是否一定存在相异代表系？
查看练习答案与解析
答案：是。根据 Hall 定理，只要满足对任意 $$k$$ 个集合，其并集大小 $| \cup S_i | \ge k$ 即可。

《离散数学》第一学期期末试卷C (精选07) ​

一、选择题(每题2分，共20分) ​

二、填空题(每题2分，共20分) ​

三、综合题(第1~6题每题8分，第7题12分，共60分) ​

《离散数学》第一学期期末试卷C (精选07)

一、选择题(每题2分，共20分)

二、填空题(每题2分，共20分)

三、综合题(第1~6题每题8分，第7题12分，共60分)